#include <string>
#include <vector>
using namespace std;
class Trie
{
private:
    struct node
    {
        node(char ch = 0, node *next_node = nullptr, size_t end_num = 0)
            : c(ch), count_end(end_num), sons(26, nullptr) { ; }

    private:
        char c;
        vector<node *> sons;
        size_t count_end;

    public:
        bool have_son(char ch)
        {
            return sons[ch - 'a'] != nullptr;
        }
        node *get_son(char ch)
        {
            return sons[ch - 'a'];
        }
        node *create_son(char ch)
        {
            return sons[ch - 'a'] = new node(ch);
        }
        bool add_end()
        {
            ++count_end;
            return true;
        }
        size_t check_ends()
        {
            return count_end;
        }
    };
    node *root;

public:
    /** Initialize your data structure here. */
    Trie() : root(new node())
    {
    }

    /** Inserts a word into the trie. */
    void insert(string word)
    {
        node *cur = root;
        for (auto e : word)
        {
            if (cur->have_son(e))
                cur = cur->get_son(e);
            else
                cur = cur->create_son(e);
        }
        cur->add_end();
    }

    /** Returns if the word is in the trie. */
    bool search(string word)
    {
        node *cur = root;
        for (auto e : word)
        {
            if (cur->have_son(e))
                cur = cur->get_son(e);
            else
                return false;
        }
        return cur->check_ends();
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix)
    {
        node *cur = root;
        for (auto e : prefix)
        {
            if (cur->have_son(e))
                cur = cur->get_son(e);
            else
                return false;
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */